/*
 * @lc app=leetcode id=25 lang=cpp
 *
 * [25] Reverse Nodes in k-Group
 */
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* reverseKGroup(ListNode* head, int k) {
        if (!head) {
            return head;
        }

        ListNode *fakeHead = new ListNode(-1);
        fakeHead->next = head;

        ListNode *prev = fakeHead;
        ListNode *node = fakeHead->next;
        ListNode *next = NULL;

        int n = 0;
        while(1) {
            n = k;
            next = NULL;
            while(node && --n) {
                node = node->next;
            }
            if (n > 0) {
                break;
            }

            // save next
            next = node->next;

            // reverse
            prev->next = reverse(prev->next, next);

            // find new prev
            node = prev->next;
            while(node->next != next) {
                node = node->next;
            }
            prev = node;

            // goto next k nodes 
            node = next;
        }

        node = fakeHead->next;
        delete fakeHead;
        return node;
    }

    ListNode *reverse(ListNode *start, ListNode *next) {
        ListNode *prev = NULL, *tmp = NULL;
        ListNode *tail = NULL;
        ListNode *node = start;

        while(node != next) {

            if (!tail) {
                tail = node;
            }

            tmp = node->next;
            node->next = prev;
            prev = node;
            node = tmp;
        }
        tail->next = next;
        return prev;
    }
};

